package com.cuz.daileetcode.h100;

import com.cuz.daileetcode.utils.TreeNode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class P297 {
    public static void main(String[] args) {
        //[1,2,3,null,null,4,5]

        TreeNode t1 = new TreeNode(1);
        TreeNode t2 = new TreeNode(2);
        TreeNode t3 = new TreeNode(3);
        TreeNode t4 = new TreeNode(4);
        TreeNode t5 = new TreeNode(5);
        t1.left = t2;
        t1.right = t3;

        t3.left = t4;
        t3.right = t5;
        String serialize = new P297().serialize(t1);
        System.out.println(serialize);

        TreeNode deserialize = new P297().deserialize(serialize);
        System.out.println(deserialize);
    }

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        if (root == null) {
            return list.toString();
        }
        preSerialize(root, list);
        return list.toString();
    }

    void preSerialize(TreeNode root, List<Integer> list) {
        if (root == null) {
            list.add(null);
            return;
        }
        list.add(root.val);

        preSerialize(root.left, list);
        preSerialize(root.right, list);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == null) {
            return null;
        }
        if (data.length() <= 2) {
            return null;
        }

        String seq = data.substring(1, data.length() - 1);
        String[] nodes = seq.split(",");
        if (nodes.length == 0) {
            return null;
        }
        LinkedList<String>l = new LinkedList<>(Arrays.asList(nodes));
        return preDeserialize(l);
    }

    TreeNode preDeserialize(LinkedList<String>l) {

        if(l.isEmpty()){
            return null;
        }
        String s = l.removeFirst();
        if (s==null){
            return null;
        }
        s = s.trim();
        if (s.equals("null")){
            return  null;
        }
        TreeNode t = new TreeNode(Integer.parseInt(s));
        t.left = preDeserialize(l);
        t.right = preDeserialize(l);
        return t;
    }

}
